#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define maxn 100001
#define inf 0x7fffffff
/**
 *  借助优先队列优化Dijkstra算法 
 */
int n, m, s, u, v, w;
struct node
{
    int to, val;
    bool operator<(const node &p) const { return val > p.val; }
    node(int to = -1, int val = inf) : to(to), val(val){};
};
int dis[maxn], vis[maxn];
vector<vector<node> > edge;
priority_queue<node> que;
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    edge.resize(n + 1);
    fill(dis, dis + n + 1, inf);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        edge[u].push_back(node(v, w));
    }
    dis[s] = 0;
    que.push(node(s, 0));
    while (!que.empty())
    {
        node nd = que.top();
        que.pop();
        if (vis[nd.to] == 1)
            continue;
        vis[nd.to] = 1;
        for (int i = 0; i < edge[nd.to].size(); ++i)
        {
            node tmp = edge[nd.to][i];
            dis[tmp.to] = min(dis[tmp.to], dis[nd.to] + tmp.val);
            if (vis[tmp.to] == 0)
            {
                que.push(node(tmp.to, dis[tmp.to]));
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", dis[i]);
    return 0;
}